
#include <iostream>
#include <math.h>
#include <fstream>
#include <sys/time.h>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <set>
#include <cstdlib> //for rand on Linux




using namespace std;

typedef struct {
	int length;
	int * tour;
} tour ;

/**
 * Finds nearest neighbor of current node that has not yet been visited
 */
int find_next_node(int &current_node , int ** adj , bool * visited , int &number_of_nodes) {
	int min = -1;
	for (int i=0; i<number_of_nodes; i++) {
		if (!visited[i] && i != current_node) {
			if (min == -1 || adj[current_node][i] < adj[current_node][min])
				min = i;
		}
	}

	return min;
}

/*
 * Prints result of init phase of tsp algorithm (NN-part)
 */
void print_tour(int & number_of_nodes, int  permutation[], int & current_tour_length)
{
    cout << "Tour: ";
    for(int i = 0;i < number_of_nodes + 1;i++){
        cout << permutation[i] << " ";
    }
    cout << endl;
    cout << "Tour length: " << current_tour_length << endl;
}

/**
 * Run nearest neighbor heuristic and return permutation of nodes (=tour)
 */
int* NN_tsp (int &start_node , int ** adj , int * permutation,  int &number_of_nodes , int &current_tour_length) {

	int current_node = start_node;
	//define and initialise visited array
	bool visited[number_of_nodes];
	for (int i=0;i<number_of_nodes;i++) visited[i] = false;

	visited[start_node] = true;

	//Tour on the graph (length n+1 since start node shows up twice)

	permutation[0] = start_node;

	//run NN
	for (int i=1;i<number_of_nodes;i++) {
		//Finds nearest neighbor
		permutation[i] = find_next_node(current_node , adj, visited , number_of_nodes);
		current_tour_length += adj[current_node][permutation[i]];
		current_node = permutation[i];
		visited[current_node] = true;
	}

	//Add last element of tour (start_node again)
	current_tour_length += adj[current_node][start_node];
	permutation[number_of_nodes] = start_node;

	return permutation;
}


/**
 * Swaps 2 elements of an int array
 */
void swap (int* &permutation , int &i , int &j) {
	int swap = permutation[j];
	permutation[j] = permutation[i];
	permutation[i] = swap;
}

/**
 * Compute delta if positions i and j are exchanged
 */
int delta(int **& adj, int* permutation, int & i, int & j) {

    int delta = -adj[permutation[i]][permutation[i - 1]];
    delta -= adj[permutation[i]][permutation[i + 1]];
    delta -= adj[permutation[j]][permutation[j - 1]];
    delta -= adj[permutation[j]][permutation[j + 1]];

    swap(permutation , i , j);

    delta += adj[permutation[j]][permutation[j - 1]];
    delta += adj[permutation[j]][permutation[j + 1]];
    delta += adj[permutation[i]][permutation[i - 1]];
    delta += adj[permutation[i]][permutation[i + 1]];

    swap(permutation , i , j);

    return delta;
}

/**
 * Returns random double between fMin and fMax
 */
double fRand(double fMin, double fMax) {
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

/**
 * Computes length of tour permutation
 */
int compute_tour_length(int * permutation , int** adj , int number_of_nodes) {
	int current_node = permutation[0];
	int length = 0;
	for (int i=1; i<= number_of_nodes; i++) {
		length += adj[current_node][permutation[i]];
		current_node = permutation[i];
	}

	return length;
}

//int tsp(int number_of_nodes , int **adj , double T , int k, int l, double a) {

tour tsp(int number_of_nodes , int **adj) {


	double T = 100000;
	int k = 100 * number_of_nodes;
	int l = 10 * number_of_nodes;
	double a=0.99;

	srand ( time(NULL) );

	int start_node = rand() % number_of_nodes;

	int current_tour_length = 0;
	int permutation[number_of_nodes+1];

	//Start NN phase of algorithm
	NN_tsp(start_node , adj , permutation , number_of_nodes , current_tour_length);


    //Keep track of minimal reached value
    int current_min_val = current_tour_length;
    int min_permutation[number_of_nodes+1];
    memcpy (min_permutation, permutation, sizeof (permutation)) ;

    //number of unsuccessful until algorithm stops
    int break_after = 1;

    int no_change_runs = 0;

    int i = 0;

    //while (no_change_runs < break_after) {
    while ( no_change_runs < break_after ) {
    	i++;

    	no_change_runs++;

    	int steps = 0;
    	int successful_steps = 0;

    	while (steps < k && successful_steps < l) {

        	//Choose 2 elements randomly
        	int i = rand() % (number_of_nodes-1) + 1;
        	int j = rand() % (number_of_nodes-1) + 1;
        	//Change j until i != j
        	while (i == j) {
        		j = rand() % (number_of_nodes-1) + 1;
        	}


        	int delta_val = delta(adj, permutation, i, j);

        	//If new permutation is better than before save it
        	if (delta_val <= 0 || (delta_val > 0 && pow(exp(1) , -delta_val/T) > fRand(0,1))) {
        		//If our solution improved or stayed the same we consider this a success
        		if (delta_val <= 0 )
        			successful_steps++;

        		//Swap position i and j
        		int swap = permutation[j];
        		permutation[j] = permutation[i];
        		permutation[i] = swap;

        		//reset counter for runs where no change occurred
        		no_change_runs = 0;
        		//update tour length
        		current_tour_length += delta_val;

        		//If the new tour length is smaller that the smallest that we saw so far save it
        		if (current_min_val > current_tour_length) {
        		    current_min_val = current_tour_length;
        			memcpy (min_permutation, permutation, sizeof (permutation)) ;
        		}
        	}

        	steps++;
    	}

    	//lower temperature
    	T = a*T;
    }

    //Print smallest tour that we saw
    print_tour(number_of_nodes , min_permutation , current_min_val);

    tour t;
    t.length = current_min_val;
    t.tour = min_permutation;

    return t;

}


int main(int argc, char *argv[]) {

	int number_of_nodes;

	// Path of the txt file
	string file;

	if (argc > 1) {
		file = argv[1];

	} else {
		file = "./input/tsp1.in";
	}

	const char *text_file = file.c_str();

	// Getting the text from the file
	string text;

	std::ifstream text_stream(text_file);



	if (text_stream.is_open()) {

		//Number of nodes in first line
	    getline(text_stream , text , '\n');

	    number_of_nodes = atoi(text.c_str());
	    //cout << "Number of nodes: " << number_of_nodes << endl;

	    //Define a number_of_nodes x number_of_nodes Matrix
	    int **adj;
	    adj = new int *[number_of_nodes];
	    for(int i = 0; i <number_of_nodes; i++)
	        adj[i] = new int[number_of_nodes];

	    int k = 0;
	    while (!text_stream.eof()) {

	    	getline(text_stream , text , '\n');
	    	//cout << text << endl;


	    	//Split String text at whitespaces
	        char * buffer = new char[text.length()+1]; //+1 fixed mem corruption for input #2


	        strcpy(buffer,text.c_str());


	        int i = 0;

	        const char* p;

	        for (p = strtok(buffer, " ");  p;  p = strtok( NULL, " " )){
	            adj[k][i] = atoi(p);
	            adj[i][k] = atoi(p);
	            i++;
	        }

	        k++;

	    }



	    tsp(number_of_nodes , adj);

	    //Prints adj Matrix (for debugging)
	    /*for (int i = 0;i<number_of_nodes;i++) {
	    	for (int k = 0;k<number_of_nodes;k++) {
	    		cout << adj[i][k] << " " ;
	    	}
	    	cout << endl;
	    }*/

		text_stream.close();
	}
	else {
		std::cout << "[Error] Unable to open file "<< argv[1] << std::endl;
		return 0;
	}

	return 0;
}
